package com.shindo.novie.class04;

/**
 * 用双向链表结构实现双端队列
 * 注意：
 * 单项链表无法实现双端队列，因为从尾部删除元素，单向链表无法再O(1)的复杂度下找到前一个节点成为新的尾节点。
 */
public class Code03_DoubleLinkListToDeQue {

    //节点定义
    public static class Node<V> {
        public V value;
        //前节点
        public Node<V> last;
        //后节点
        public Node<V> next;

        public Node(V v) {
            value = v;
            last = null;
            next = null;
        }
    }

    /**
     * 实现双端队列
     */
    public static class MyDeque<V> {
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyDeque() {
            head = null;
            tail = null;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        //从头添加元素
        public void pushHead(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                //新节点的后节点连上原头节点，新节点的前节点默认为null
                cur.next = head;
                //原头节点的前节点连上新节点
                head.last = cur;
                //头节点指向新头
                head = cur;
            }
            size++;
        }

        //从尾部添加元素
        public void pushTail(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                //原尾节点的后节点连上新节点
                tail.next = cur;
                //新节点的前指针连上原尾节点，新节点的后指针默认为null
                cur.last = tail;
                //尾节点指向新尾
                tail = cur;
            }
            size++;
        }

        //从头部取元素
        public V pollHead() {
            V ans = null;
            if (head == null) {
                return null;
            }
            size--;
            ans = head.value;
            //如果队列仅剩最后一个元素，取出元素后要清空队列
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                //头节点指向下一个节点，成为新的头
                head = head.next;
                //新头的前指针调整为null
                head.last = null;
            }
            return ans;
        }

        //从尾部取元素
        public V pollTail() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                //尾节点指向前一个节点，成为新的尾
                tail = tail.last;
                //新尾的后指针调整为null
                tail.next = null;
            }
            return ans;
        }

        //查看头元素
        public V peekHead() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }

        //查看尾元素
        public V peekTail() {
            V ans = null;
            if (tail != null) {
                ans = tail.value;
            }
            return ans;
        }
    }

}
